The Tangent-Graeffe root finding algorithm

Abstract: Let $f(x)$ be a polynomial of degree $d$ over a prime field of size $p$. Suppose $f(x)$ has $d$ distinct roots in the field and we want to compute them. Question: How fast can we compute the roots?

The most well known method is the Cantor-Zassenhaus algorithm from 1981. It is implemented in Maple and Magma. It does, on average, $O(M(d) \log d \log p)$ arithmetic operations in the field where $M(d)$ is the cost of multiplying two polynomials of degree $\le d$.

In 2015 Grenet, van der Hoeven and Lecerf found a beautiful new method for the case $p = s 2^k + 1$ with $s \in O(d)$. The new method improves on Cantor-Zassenhaus by a factor of $O(\log d)$. Our contribution is a speed up for the core computation of the new method by a constant factor and a C implementation of the new method using asymptotically fast polynomial arithmetic.

In the talk I will present the main ideas behind the new Tangent-Graeffe algorithm, some timings comparing the Tangent Graeffe algorithm with the Cantor-Zassenhaus algorithm in Magma, and a new polynomial factorization world record.

This is joint work with Joris van der Hoeven.

algebraic geometrynumber theory

Audience: researchers in the topic

---

SFU NT-AG seminar

Series comments: The Number Theory and Algebraic Geometry (NT-AG) seminar is a research seminar dedicated to topics related to number theory and algebraic geometry hosted by the NT-AG group (Nils Bruin, Imin Chen, Stephen Choi, Katrina Honigs, Nathan Ilten, Marni Mishna).

We acknowledge the support of PIMS, NSERC, and SFU.

For Fall 2025, the organizers are Katrina Honigs and Peter McDonald.

We normally meet in-person in the indicated room. For online editions, we use Zoom and distribute the link through the mailing list. If you wish to be put on the mailing list, please subscribe to ntag-external using lists.sfu.ca

---